package _interview150;

import java.util.HashMap;
import java.util.Map;

/**
 * 76. 最小覆盖子串
 */
public class No76 {
    private Map<Character, Integer> origin;
    private Map<Character, Integer> curMap;

    public String minWindow(String s, String t) {
        origin = new HashMap<>();
        for (char c : t.toCharArray()) origin.put(c, origin.getOrDefault(c, 0) + 1);

        curMap = new HashMap<>();

        int start = 0, end = -1;
        String ans = s + "?";
        while (end < s.length() - 1) {
            end++;
            char c = s.charAt(end);
            if (origin.containsKey(c)) {
                curMap.put(c, curMap.getOrDefault(c, 0) + 1);
            }
            while (isValid()) {
                String substring = s.substring(start, end + 1);
                if (substring.length() < ans.length()) ans = substring;
                if (curMap.containsKey(s.charAt(start))) {
                    curMap.put(s.charAt(start), curMap.get(s.charAt(start)) - 1);
                }
                start++;
            }
        }
        return ans.length() == s.length() + 1 ? "" : ans;
    }

    private boolean isValid() {
//        return origin.entrySet().stream().allMatch(entry -> curMap.containsKey(entry.getKey()) && curMap.get(entry.getKey()) >= entry.getValue());
        for (Map.Entry<Character, Integer> entry : origin.entrySet()) {
            Character key = entry.getKey();
            Integer value = entry.getValue();
            if (!curMap.containsKey(key) || curMap.get(key) < value) return false;
        }
        return true;
    }
}
